/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package ua.yandex.mergesort;

import static java.lang.Math.max;
import java.util.List;

/**
 *
 * @author Neophron
 * @param <E>
 */
public class Merge<E extends Comparable<E>> implements Runnable {

    private final List<E> A, T;
    private int p1, r1, p2, r2, p3;

    Merge(List<E> T, int p1, int r1, int p2, int r2, List<E> A, int p3) {
        this.T = T;
        this.A = A;
        this.p1 = p1;
        this.p2 = p2;
        this.p3 = p3;
        this.r1 = r1;
        this.r2 = r2;
    }

    private int binarySearch(E x, int p, int r) {
        int low = p;
        int high = max(p, r + 1);
        while (low < high) {
            int mid = (low + high) / 2;
            if (x.compareTo(T.get(mid)) < 0) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return high;
    }

    @Override
    public void run() {
        int n1 = r1 - p1 + 1;
        int n2 = r2 - p2 + 1;
        if (n1 < n2) {
            int tmp = r1;
            r1 = r2;
            r2 = tmp;
            tmp = p1;
            p1 = p2;
            p2 = tmp;
            n1 = n2;
        }
        if (n1 == 0) {
            return;
        }
        int q1 = (r1 + p1) / 2;
        int q2 = binarySearch(T.get(q1), p2, r2);
        int q3 = p3 + (q1 - p1) + (q2 - p2);
        A.set(q3, T.get(q1));
        Thread t1 = new Thread(new Merge<>(T, p1, q1 - 1, p2, q2 - 1, A, p3));
        Merge t2 = new Merge<>(T, q1 + 1, r1, q2, r2, A, q3 + 1);
        t1.start();
        t2.run();
        try {
            t1.join();
        } catch (InterruptedException ex) {
        }
    }

}
